﻿//#define _CRT_SECURE_NO_WARNINGS 1
//
//#include <iostream>
//#include <vector>
//#include <string>
//#include <algorithm>
//
//using namespace std;
//
//class Solution
//{
//public:
//	int longestPalindrome(string s)
//	{
//		// 1. 计数-⽤数组模拟哈希表
//		int hash[127] = { 0 };
//		for (char ch : s) hash[ch]++;
//		// 2. 统计结果
//		int ret = 0;
//		for (int x : hash)
//		{
//			ret += x / 2 * 2;
//		}
//		return ret < s.size() ? ret + 1 : ret;
//	}
//};
//
//
//class Solution
//{
//public:
//	vector<int> diStringMatch(string s)
//	{
//		int left = 0, right = s.size(); // ⽤left，right标记最⼩值和最⼤值
//		vector<int> ret;
//		for (auto ch : s)
//		{
//			if (ch == 'I') ret.push_back(left++);
//			else ret.push_back(right--);
//		}
//		ret.push_back(left); // 把最后⼀个数放进去
//		return ret;
//	}
//};
//
//class Solution
//{
//public:
//	int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
//	{
//		int n = gas.size();
//		for (int i = 0; i < n; i++) // 依次枚举所有的起点
//		{
//		int rest = 0; // 标记⼀下净收益
//		int step = 0;
//		for (; step < n; step++) // 枚举向后⾛的步数
//
//		{
//			int index = (i + step) % n; // 求出⾛ step步之后的下标
//
//				rest = rest + gas[index] - cost[index];
//				if (rest < 0) break;
//		}
//		if (rest >= 0) return i;
//		i = i + step; // 优化
//		}
//		return -1;
//	}
//};